/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package phd.dupenois.changeidentifiers.algorithms.chihull;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import phd.dupenois.changeidentifiers.algorithms.chihull.display.DelaunayGrid;
import uk.co.dupenois.geometry.Circle;
import uk.co.dupenois.geometry.Coordinate;
import uk.co.dupenois.geometry.Edge;
import uk.co.dupenois.geometry.Line;

/**
 *
 * @author mpd209
 */
public class DivideAndConquerDelaunayTriangulationEngine {

    private ArrayList<Coordinate> xSortedCoordinateList;
    private DelaunayTriangulation finishedTriangulation;
    private DelaunayGrid debugGrid;
    public static long PAUSE = 0;
    public static boolean DRAW_ONLY_FINISHED = false;
    public static Coordinate coordinateOfInterest = null;


    public DivideAndConquerDelaunayTriangulationEngine(
            ArrayList<Coordinate> xSortedCoordinateList) {
        this(xSortedCoordinateList, false, null);
    }


    public DivideAndConquerDelaunayTriangulationEngine(
            ArrayList<Coordinate> xSortedCoordinateList, DelaunayGrid debugGrid) {
        this(xSortedCoordinateList, false, debugGrid);
    }

    public DivideAndConquerDelaunayTriangulationEngine(
            ArrayList<Coordinate> coordinateList, boolean sort) {
        this(coordinateList, sort, null);
    }

    public DivideAndConquerDelaunayTriangulationEngine(
            ArrayList<Coordinate> coordinateList, boolean sort, DelaunayGrid debugGrid) {
        if (sort) {
            Collections.sort(coordinateList, new Comparator<Coordinate>(){
                public int compare(Coordinate arg0, Coordinate arg1) {
                    return arg0.compareByMinXMinY(arg1);
                }
            });
        }
//        this.xSortedCoordinateList = coordinateList;
        this.xSortedCoordinateList = new ArrayList<Coordinate>();
        //Remove duplicates
        for(Coordinate c : coordinateList){
            if(!this.xSortedCoordinateList.contains(c)){
                this.xSortedCoordinateList.add(c);
            }
        }
        this.debugGrid = debugGrid;

    }
//    private static void pause(){
//        pause(PAUSE);
//    }
//    private static void pause(long amount){
//        try{
//            Thread.sleep(amount);
//        }catch(InterruptedException ex){}
//    }
//
//    public boolean hasCoordinateOfInterest(DelaunayTriangulation triangulation){
//        //If debug return true anyway
//        if(isDebug()) return true;
//        if(coordinateOfInterest==null) return false;
//        boolean found = false;
//        Coordinate[] coords = triangulation.getCoordinates();
//        for(int i=0; !found && i<coords.length; i++){
//            found = (coords[i].equalsCheck(coordinateOfInterest));
//        }
//        return found;
//    }
//    public boolean hasCoordinateOfInterest(DelaunayTriangle triangle){
//        //If debug return true anyway
//        if(isDebug()) return true;
//        if(coordinateOfInterest==null) return false;
//        boolean found = false;
//        Coordinate[] coords = triangle.getVertices();
//        for(int i=0; !found && i<coords.length; i++){
//            found = (coords[i].equalsCheck(coordinateOfInterest));
//        }
//        return found;
//    }
//    public boolean hasCoordinateOfInterest(Edge edge){
//        //If debug return true anyway
//        if(isDebug()) return true;
//        if(coordinateOfInterest==null) return false;
//        return (edge.getStart().equalsCheck(coordinateOfInterest)
//                ||edge.getFinish().equalsCheck(coordinateOfInterest));
//    }
//
//    public boolean isDebug(){
////        return false;
//        return (!DRAW_ONLY_FINISHED&&this.debugGrid!=null);
//    }
//    public void debugOut(String debug){
//        debugOut(debug, isDebug());
//    }
//    public void debugOut(String debug, boolean show){
//        if(show) whereAmI(debug);
//    }

    public void whereAmI(String str){
        StackTraceElement[] trace = Thread.currentThread().getStackTrace();
        StackTraceElement location;
        int lineNumber = 0;
        String methodName = "debugOut";
        for(int i = 2; methodName.equals("debugOut")&&i <trace.length; i++){
            location = trace[i];
            lineNumber = location.getLineNumber();
            methodName = location.getMethodName();
        }
        System.out.println("["+lineNumber+"]:: "+str);
    }

    public DelaunayTriangulation triangulate(){
        this.finishedTriangulation = constructTriangulation(xSortedCoordinateList);
//        if(isDebug()||(DRAW_ONLY_FINISHED&&this.debugGrid!=null)) {
//            debugOut("Finished Triangulation", (DRAW_ONLY_FINISHED&&this.debugGrid!=null));
//            this.debugGrid.drawMergedTriangulation(finishedTriangulation);
//        }
        return this.finishedTriangulation;
    }

    public DelaunayTriangulation constructTriangulation(ArrayList<Coordinate> list){
        DelaunayTriangulation triangulation;
        if(list.size()>3){
            ArrayList<ArrayList<Coordinate>> lists = split(list);
            ArrayList<Coordinate> left = lists.get(0);
            ArrayList<Coordinate> right = lists.get(1);
            DelaunayTriangulation triangulationLeft = constructTriangulation(left);
            
            DelaunayTriangulation triangulationRight = constructTriangulation(right);

            triangulation = mergeTriangulations(triangulationLeft, triangulationRight);

//            if(isDebug()){
//                debugOut("Merged");
//                this.debugGrid.drawMergedTriangulation(triangulation);
//                pause();
//            }

        }else{
            triangulation = new DelaunayTriangulation();
            DelaunayTriangle triangle = null;
            if(list.size()==3){
                triangle = new DelaunayTriangle(list.get(0), list.get(1), list.get(2), true);
            }else if(list.size()==2){
                triangle = new DelaunayTriangle(list.get(0), list.get(1), true);
            }
            if(triangle!=null) triangulation.addTriangle(triangle);
        }

        return triangulation;
    }


    private ArrayList<ArrayList<Coordinate>> split(ArrayList<Coordinate> list){
        
        int size = list.size();
        int half = (int)Math.floor((double)size/2d);
        ArrayList<Coordinate> left = new ArrayList<Coordinate>();
        ArrayList<Coordinate> right = new ArrayList<Coordinate>();
        left.addAll(list.subList(0, half));
        right.addAll(list.subList(half, size));
        ArrayList<ArrayList<Coordinate>> result = new ArrayList<ArrayList<Coordinate>>();
        result.add(left);
        result.add(right);
        return result;
    }

    public boolean allTriangulationPointsOnLine(DelaunayTriangulation left,
            DelaunayTriangulation right){
        Coordinate[] coordsLeft = left.getCoordinates();
        Coordinate[] coordsRight = right.getCoordinates();
        boolean differentXFound = false;
        double diff;
        for(int l = 0; !differentXFound&&l<coordsLeft.length;l++){
            for(int r = 0; !differentXFound&&r<coordsRight.length;r++){
                diff = Math.abs(coordsLeft[l].getX()-coordsRight[r].getX());
                differentXFound = (diff>0.00009);
            }
        }
        return !differentXFound;
    }

    public Edge getBaseline(DelaunayTriangulation left,
            DelaunayTriangulation right){
        //First find baseline
        //Minor issue can happen here
        /*
         *          \
         *           o(100, 100)
         *
         *
         *       o (50, 50)
         *      /
         *    o (34, 35)
         * Baseline tries to draw from (34, 35) to (100, 100), these maybe the
         * lowest vertices but it puts it above the line (34,35) to (50,50)
         * So the wanted baseline would be (50, 50) to (100,100)
         * We can test by checking that all dots are to the left of the
         * line (left because line goes from left triangulation to right triangulation)
         * at the start, in practice we probably only needed to check vertices
         * attached to baselineLeft and baselineRight
         * Also can have an issue if points are on the line
        */
        Coordinate baselineLeft = left.getCurrentLowestVertexRight();
        Coordinate baselineRight = right.getCurrentLowestVertexLeft();
//        debugOut("\tRight All : ");
//        for(Coordinate v : right.getCoordinates()) debugOut("\t\t"+v);
        Edge baseline = new Edge(baselineLeft, baselineRight);
//        debugOut("Potential Baseline: "+baseline);
        Coordinate[] leftCoordinates;
        Coordinate[] rightCoordinates;
        Coordinate leftCoordToCheck;
        Coordinate rightCoordToCheck;
        boolean baseLineValid = false;
        boolean baseLinePossiblyValid;
        boolean onLineCheck = false;
        boolean onLineAndRefindRequired = false;
        boolean leftBelowRight = false;
//        whereAmI("Before BaselineValid");
//        int count=0;
        while(!baseLineValid){
            baseLinePossiblyValid = true;
//            leftCoordinates = left.getCoordinates();
            leftCoordinates = left.getCoordinatesAttachedTo(baselineLeft);
            for(int i=0; baseLinePossiblyValid&&i<leftCoordinates.length; i++){
                leftCoordToCheck = leftCoordinates[i];
                onLineCheck = false;
                onLineAndRefindRequired = false;
                //Okay check whether left is below right or vice versa
                leftBelowRight = baselineRight.getY()>baselineLeft.getY();
                if(baseline.isOnEdge(leftCoordToCheck)){
                    onLineCheck = true;
                    onLineAndRefindRequired =
                            (leftBelowRight&&leftCoordToCheck.getY()>baselineLeft.getY())||
                            (!leftBelowRight&&leftCoordToCheck.getY()<baselineLeft.getY());
                }
                if(onLineAndRefindRequired||(!onLineCheck&&baseline.isCoordinateRightOfLine(leftCoordToCheck))){
//                    System.out.println("Coordinate from left is right of or on line: "+leftCoordToCheck);
//                    debugOut("!LEFT: Coordinate "+(onLineAndRefindRequired?"on line":"right of")
//                            + " "+leftCoordToCheck+" Old Baseline:"+baselineLeft+"->"+baselineRight);
                    baseLinePossiblyValid = false;
                    baselineLeft = leftCoordToCheck;
                }
            }
            if(baseLinePossiblyValid){
//                rightCoordinates = left.getCoordinates();
                rightCoordinates = right.getCoordinatesAttachedTo(baselineRight);
                for(int i=0; baseLinePossiblyValid&&i<rightCoordinates.length; i++){
                    rightCoordToCheck = rightCoordinates[i];
                    onLineCheck = false;
                    onLineAndRefindRequired = false;
                    if(baseline.isOnEdge(rightCoordToCheck)){
                        onLineCheck = true;
                        onLineAndRefindRequired =
                            (!leftBelowRight&&rightCoordToCheck.getY()>baselineRight.getY())||
                            (leftBelowRight&&rightCoordToCheck.getY()<baselineRight.getY());
                    }
//                    debugOut("!CHECKING "+rightCoordToCheck+" "+(onLineCheck?"":"NOT")+" on line and redraw "+(onLineAndRefindRequired?"":"NOT")+" above");
                    if(onLineAndRefindRequired||(!onLineCheck&&baseline.isCoordinateRightOfLine(rightCoordToCheck))){
//                        System.out.println("Coordinate from right is right of or on line: "+rightCoordToCheck);
//                        debugOut("!RIGHT: Coordinate "+(!onLineAndRefindRequired?"on line":"right of")
//                                +": "+rightCoordToCheck+" Old Baseline:"+baselineLeft+"->"+baselineRight);
                        baseLinePossiblyValid = false;
                        baselineRight = rightCoordToCheck;
                    }
                }
            }
            if(!baseLinePossiblyValid){
                //Get next
                baseline = new Edge(baselineLeft, baselineRight);

//                debugOut("New BaseLine "+baselineLeft+"->"+baselineRight);
            }else{
                baseLineValid = true;
            }
//            count++;
        }
        return baseline;
    }

    public DelaunayTriangulation mergeTriangulations(DelaunayTriangulation left,
            DelaunayTriangulation right){

//        long mergeStartTime = System.currentTimeMillis();
//        String timerCount = "**MERGE**\n";
//        boolean hasCandidateOfInterest = hasCoordinateOfInterest(left)||hasCoordinateOfInterest(right);
//        if(isDebug()||hasCandidateOfInterest){
//            debugOut("----------START MERGE----------",
//                    hasCandidateOfInterest);
//            this.debugGrid.drawLeftTriangulation(left);
//            this.debugGrid.drawRightTriangulation(right);
//            pause();
//        }

//         long startTime = System.currentTimeMillis();
         Edge baseline = getBaseline(left, right);
         Coordinate baselineRight = baseline.getFinish();
         Coordinate baselineLeft = baseline.getStart();
//         timerCount+="[DT] Get Baseline Took: "+(System.currentTimeMillis()-startTime)+" ms\n";


//        if(isDebug()){
//            this.debugGrid.drawBaseline(baseline);
//            pause();
//        }

        Edge[] rightEdges = right.getEdgesRightToLeft();
        Edge[] leftEdges = left.getEdgesLeftToRight();


//        startTime = System.currentTimeMillis();
        //Get Candidate from right first
        PotentialCandidate potentialCandidateRight = getPotentialCandidate(baselineRight, baseline, rightEdges, false);
//        if(isDebug()){
//            if(potentialCandidateRight!=null){
//                this.debugGrid.drawCandidateRight(potentialCandidateRight.getCandidate());
//                pause();
//            }
//        }
        PotentialCandidate potentialCandidateLeft = getPotentialCandidate(baselineLeft, baseline, leftEdges, true);
//        if(isDebug()){
//            if(potentialCandidateLeft!=null){
//                this.debugGrid.drawCandidateLeft(potentialCandidateLeft.getCandidate());
//                pause();
//            }
//        }
//        timerCount+="[DT] Get Candidates Took: "+(System.currentTimeMillis()-startTime)+" ms\n";

        if(potentialCandidateRight==null&&potentialCandidateLeft==null){
            //Still need to draw the baseline even if we never loop
//            debugOut("Degenerate baseline", hasCandidateOfInterest);

            left.addTriangle(new DelaunayTriangle(baselineLeft, baselineRight));
        }

        DelaunayTriangle newTriangle = null;
        Edge newBaseline =null;
        ArrayList<Line> edgesToRemove = new ArrayList<Line>();

//        startTime = System.currentTimeMillis();
//        int loopCount = 0;
//        long loopInternalTimer;
        while(potentialCandidateRight!=null||potentialCandidateLeft!=null){

//            debugOut("--LOOP--", hasCandidateOfInterest);

//            loopInternalTimer = System.currentTimeMillis();
            boolean addToLeft = false;
            if(potentialCandidateLeft==null){
//                debugOut("Left candidate is null", hasCandidateOfInterest);
                //Use right
                newTriangle = new DelaunayTriangle(baselineLeft, baselineRight, potentialCandidateRight.getCandidate());
                newBaseline = new Edge(baselineLeft, potentialCandidateRight.getCandidate());
                potentialCandidateRight.addEdgesToRemove(edgesToRemove);
                addToLeft = false;

            }else if(potentialCandidateRight==null){
//                debugOut("Right candidate is null", hasCandidateOfInterest);
                //use left
                newTriangle = new DelaunayTriangle(baselineLeft, baselineRight, potentialCandidateLeft.getCandidate());
                newBaseline = new Edge(baselineRight, potentialCandidateLeft.getCandidate());
                potentialCandidateLeft.addEdgesToRemove(edgesToRemove);
                addToLeft = true;

            }else{
                //Circle with right
                boolean rightContainsLeft = circleContainsNext(baseline, potentialCandidateRight.getCandidate(), potentialCandidateLeft.getCandidate());
                
//                debugOut("Checking if circle on right candidate "+
//                        potentialCandidateRight.getCandidate()+
//                        " contains left candidate "+
//                        potentialCandidateLeft.getCandidate(), hasCandidateOfInterest);
                boolean leftContainsRight = true;
                if(!rightContainsLeft){
                    //use right
//                    debugOut("Right does not contain left using it", hasCandidateOfInterest);
                    newTriangle = new DelaunayTriangle(baselineLeft, baselineRight, potentialCandidateRight.getCandidate());
                    newBaseline = new Edge(baselineLeft, potentialCandidateRight.getCandidate());
                    potentialCandidateRight.addEdgesToRemove(edgesToRemove);
                    addToLeft = false;
                }else {
                    //Only need to check if not using right
                    leftContainsRight = circleContainsNext(baseline, potentialCandidateLeft.getCandidate(), potentialCandidateRight.getCandidate());
//                    debugOut("Checking if circle on left candidate "+
//                        potentialCandidateLeft.getCandidate()+
//                        " contains right candidate "+
//                        potentialCandidateRight.getCandidate(), hasCandidateOfInterest);
                }
                if(!leftContainsRight){
                    //use left
//                    debugOut("Left does not contain right using it", hasCandidateOfInterest);
                    newTriangle = new DelaunayTriangle(baselineLeft, baselineRight, potentialCandidateLeft.getCandidate());
                    newBaseline = new Edge(baselineRight, potentialCandidateLeft.getCandidate());
                    potentialCandidateLeft.addEdgesToRemove(edgesToRemove);
                    addToLeft = true;
                }else if(leftContainsRight&&rightContainsLeft){
                    //Neither Candidate is suitable
//                    debugOut("Neither candidate is suitable", hasCandidateOfInterest);
                    potentialCandidateRight = null;
                    potentialCandidateLeft = null;
                    continue;
                }
            }
//            if(isDebug()||hasCandidateOfInterest) {
//                debugOut("Proposed Triangle", hasCandidateOfInterest);
//                debugGrid.drawProposedTriangle(newTriangle.getEdges());
//                pause();
//                debugOut("New baseline", hasCandidateOfInterest);
//                debugGrid.drawNewBaseline(newBaseline);
//                pause();
//            }
//            loopInternalTimer = System.currentTimeMillis()-loopInternalTimer;
//            timerCount+="\t[DT] Selecting baseline: "+loopInternalTimer+" ms\n";
//            loopInternalTimer = System.currentTimeMillis();
            baseline = newBaseline;
            baselineLeft = baseline.getLeftCoordinate();
//            debugOut("baselineLeft: "+ baselineLeft, hasCandidateOfInterest);
            baselineRight = baseline.getRightCoordinate();
//            debugOut("baselineRight: "+ baselineRight, hasCandidateOfInterest);
//            rightEdges = right.getEdgesByVertex(baselineRight);
//            leftEdges = left.getEdgesByVertex(baselineLeft);
            rightEdges = right.getEdgesRightToLeft();
            leftEdges = left.getEdgesLeftToRight();
//            baselineRight = right.getCurrentLowestVertexLeft();
//            baseline = new Edge(baselineLeft, baselineRight, true);

//            loopInternalTimer = System.currentTimeMillis()-loopInternalTimer;
//            timerCount+="\t[DT] Got Edges: "+loopInternalTimer+" ms\n";
//            loopInternalTimer = System.currentTimeMillis();
            if(addToLeft){
                left.addTriangle(newTriangle);
//                if(isDebug()||hasCandidateOfInterest){
//                    debugOut("New Left Triangle", hasCandidateOfInterest);
//                    this.debugGrid.drawLeftTriangulation(left);
//                    pause();
//                }
            }else{
                right.addTriangle(newTriangle);
//                if(isDebug()||hasCandidateOfInterest){
//                    debugOut("New Right Triangle", hasCandidateOfInterest);
//                    this.debugGrid.drawRightTriangulation(right);
//                    pause();
//                }
            }
//            loopInternalTimer = System.currentTimeMillis()-loopInternalTimer;
//            timerCount+="\t[DT] Added  Triangle "+loopInternalTimer+" ms\n";

//            if(isDebug()||hasCandidateOfInterest){
//                debugOut("Baseline Switched", hasCandidateOfInterest);
//                this.debugGrid.drawBaseline(baseline);
//                pause();
//            }
//            loopInternalTimer = System.currentTimeMillis();
            potentialCandidateRight = getPotentialCandidate(baselineRight, baseline, rightEdges, false);
//            loopInternalTimer = System.currentTimeMillis()-loopInternalTimer;
//            timerCount+="\t[DT] Got potential Candidate Right "+loopInternalTimer+" ms\n";

//            if((isDebug()||hasCandidateOfInterest)&& potentialCandidateRight!=null){
//                this.debugGrid.drawCandidateRight(potentialCandidateRight.getCandidate());
//                pause();
//            }

//            loopInternalTimer = System.currentTimeMillis();
            potentialCandidateLeft = getPotentialCandidate(baselineLeft, baseline, leftEdges, true);
//            loopInternalTimer = System.currentTimeMillis()-loopInternalTimer;
//            timerCount+="\t[DT] Got potential Candidate Left "+loopInternalTimer+" ms\n";

//            if((isDebug()||hasCandidateOfInterest)&& potentialCandidateLeft!=null){
//                this.debugGrid.drawCandidateLeft(potentialCandidateLeft.getCandidate());
//                pause();
//            }
//            loopCount++;
        }
//        timerCount+="[DT] Loop Took: "+(System.currentTimeMillis()-startTime)+" ms, looped: "+loopCount+"\n";
//        startTime =  System.currentTimeMillis();

        left.addTriangulation(right);

//        timerCount+="[DT] Triangulation addition: "+(System.currentTimeMillis()-startTime)+" ms\n";

//        startTime =  System.currentTimeMillis();
        removeEdges(left, edgesToRemove.toArray(new Edge[edgesToRemove.size()]));
//        timerCount+="[DT] Removal: "+(System.currentTimeMillis()-startTime)+" ms\n";

//        long mergeTotalTime = System.currentTimeMillis()-mergeStartTime;
//        if(mergeTotalTime>=100) System.out.println(timerCount+"[DT] Total Merge took "+mergeTotalTime+" ms");
        return left;
    }
    private void removeEdges(DelaunayTriangulation triangulation, Edge[] edges){
        for(Edge edge : edges) {
            triangulation.removeEdge(edge);
//            if(isDebug()){
//                debugOut("Removing Edge ("+edge.getStart()+"->"+edge.getFinish()+")");
//                debugOut("Removal was a Success:"+(triangulation.getTrianglesByEdge(edge).length<1));
//                debugGrid.drawRemoveEdge(edge);
//                pause();
//            }

        }
    }

    private class PotentialCandidate{
        private Coordinate candidate;
        private Edge[] edgesToRemove;
        public PotentialCandidate(Coordinate candidate, Edge[] edgesToRemove){
            this.candidate =candidate;
            this.edgesToRemove = edgesToRemove;
        }
        public Coordinate getCandidate() {return candidate;}
        public Edge[] getEdgesToRemove() {return edgesToRemove;}
        public void addEdgesToRemove(ArrayList<Line> edgeRemovalList) {
            for(Line edge : edgesToRemove){
                edgeRemovalList.add(edge);
            }
        }
    }

    private PotentialCandidate getPotentialCandidate(Coordinate angleVertex, Edge baseline, Edge[] edges, boolean left){
        Coordinate[] possibleCoordinates = getCandidates(angleVertex, baseline, edges, left);
        if(possibleCoordinates.length<1) return null;
        if(possibleCoordinates.length==1) {
//            if(isDebug()){
//                this.debugGrid.drawCandidate(possibleCoordinates[0]);
//                debugOut("Drawn candidate");
//            }
            return new PotentialCandidate(possibleCoordinates[0],  new Edge[0]);
        }
        Coordinate potentialCoordinate = possibleCoordinates[0];
        Coordinate nextPotentialCoordinate;
        boolean isConfirmed = false;
        ArrayList<Line> edgesToRemove = new ArrayList<Line>();
        for(int i=1; !isConfirmed && i< possibleCoordinates.length;i++){
            nextPotentialCoordinate = possibleCoordinates[i];
//            if(isDebug()){
//                this.debugGrid.drawCandidate(potentialCoordinate);
//                debugOut("Drawn candidate");
//                this.debugGrid.drawNextCandidate(nextPotentialCoordinate);
//                debugOut("Drawn next candidate");
//                pause();
//            }
            if(circleContainsNext(baseline, potentialCoordinate, nextPotentialCoordinate)){
                Edge remove = new Edge(angleVertex, potentialCoordinate);
                edgesToRemove.add(remove);
//                if(isDebug()){
//                    this.debugGrid.markRemovalEdge(remove);
//                    debugOut("Previous Potential: "+potentialCoordinate);
//                    debugOut("New Potential: "+nextPotentialCoordinate);
//                    debugOut("MARKING EDGE FOR REMOVAL ("+remove.getStart()+"->"+remove.getFinish()+")");
//                    pause();
//                }
                potentialCoordinate = nextPotentialCoordinate;
                if(i==possibleCoordinates.length-1) isConfirmed = true;
            }else{
                isConfirmed = true;
            }
        }
//        //Need to remove the edge that was will included on the left
//        if(left){
//            edgesToRemove.add(new Edge(potentialCoordinate, baseline.getLeftCoordinate(), true));
//        }else{
//            edgesToRemove.add(new Edge(potentialCoordinate, baseline.getRightCoordinate(), true));
//        }
        if(!isConfirmed) return null;
        return new PotentialCandidate(potentialCoordinate, edgesToRemove.toArray(new Edge[edgesToRemove.size()]));
    }

    private boolean circleContainsNext(Line baseline, Coordinate potentialCoordinate, Coordinate nextPotentialCoordinate){
        Circle circle = new Circle(baseline.getStart(), baseline.getFinish(),
                potentialCoordinate);
//        if(isDebug()){
//            this.debugGrid.drawCandidateCheck(circle);
//            pause();
//        }
        return circle.properContainsPoint(nextPotentialCoordinate);
    }


    private class CandidateAngle implements Comparable<CandidateAngle>{
        private Coordinate coordinate;
        private double angle;
        public CandidateAngle(Coordinate coordinate, double angle){
            this.coordinate = coordinate;
            this.angle = angle;
        }
        
        public int compareTo(CandidateAngle arg1) {
            double diff = this.getAngle()-arg1.getAngle();
            if(diff<0)return-1;
            if(diff==0) return 0;
            return 1;
        }

        public Coordinate getCoordinate() {return coordinate; }

        public double getAngle() {return angle;}
        @Override
        public String toString(){
            return this.coordinate.toString(2)+" angle: "+angle+ " angle degrees "+Math.toDegrees(angle);
        }
        
    }


    private Coordinate[] getCandidates(Coordinate angleVertex, Edge baseline, Edge[] edges, boolean fromLeft){
        ArrayList<CandidateAngle> candidates = new ArrayList<CandidateAngle>();
        ArrayList<Coordinate> examinedCandidates = new ArrayList<Coordinate>();
        Coordinate edgeCoordinate;
//        debugOut("--Getting Candidates For Baseline: "+baseline.getStart()+"->"+baseline.getFinish());
        for(int i=0; i<edges.length;i++){
//            debugOut("Edge: "+edges[i].getStart()+"->"+edges[i].getFinish());
//            debugOut("From Left: "+fromLeft);
            //If the start is the angle vertex then the finish is the potential
            //candidate we'll test and vice versa,
            if(edges[i].getStart().equalsCheck(angleVertex)){
                edgeCoordinate = edges[i].getFinish();
            }else if(edges[i].getFinish().equalsCheck(angleVertex)){
                edgeCoordinate = edges[i].getStart();
            }else{
                //Only should have edges with a common vertex so should never
                //happen
                continue;
            }
//            debugOut("edgeCoordinate: "+edgeCoordinate);

            //If it's on the line no point looking at it
            if(examinedCandidates.contains(edgeCoordinate)) continue;
            if(baseline.isOnLine(edgeCoordinate)) continue;
//            if(edgeCoordinate.getX()==1359.0) System.out.println("Baseline: "+baseline.getStart()+"->"+baseline.getFinish());
//            if(edgeCoordinate.getX()==1359.0) System.out.println("Edge: "+edges[i].getStart()+"->"+edges[i].getFinish());
            
            
//            Baseline goes from left triangulation to right triangulation,
//            so we only want points to the left of it
//            if(baseline.isCoordinateLeftOfLine(edgeCoordinate)){
//                if(baseline==null)debugOut("BASELINE IS NULL");
//                if(edges[i]==null)debugOut("EDGES[i] IS NULL");
//                Edge baseLineNonSegment = new Edge(baseline.getStart(), baseline.getFinish(), false);
//                Edge edgeNonSegment = new Edge(edges[i].getStart(), edges[i].getFinish(), false);
            double angle;
            if(fromLeft){
                angle = baseline.getAngleAntiClockwiseFromMeTo(edges[i]);
            }else{
                angle = baseline.getAngleClockwiseFromMeTo(edges[i]);
            }
//            if(isDebug()){//||edgeCoordinate.getX()==1359.0
//                debugGrid.drawExaminedCoordinate(edgeCoordinate);
//                debugOut("Angle: "+angle+ " degrees "+Math.toDegrees(angle));
//                pause();
//            }
            if(angle<Math.PI){
//                if(isDebug())debugOut("Adding To Candidates");
                candidates.add(new CandidateAngle(edgeCoordinate, angle));
            }
            examinedCandidates.add(edgeCoordinate);
//            }
        }
        Collections.sort(candidates);
        Coordinate[] candidateArray = new Coordinate[candidates.size()];
//        debugOut("Candidates:-");
        for(int i=0; i< candidateArray.length;i++) {
//            debugOut(candidates.get(i).toString());
            candidateArray[i] = candidates.get(i).getCoordinate();
        }
        return candidateArray;
    }

}
